#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
// p:下标 h:堆
// h[i]存储堆中的值
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的，ph[j]=k hp[k]=j
int h[N], ph[N], hp[N], sizeh;

void heap_swap(int a, int b) // 交换两个堆中的结点
{
    swap(ph[hp[a]], ph[hp[b]]); // 交换ph指针
    swap(hp[a], hp[b]);         // 交换hp指针
    swap(h[a], h[b]);           // 交换元素
}
void up(int u)
{
    while (u / 2 && h[u / 2] > h[u]) // 直接向上交换
    {
        heap_swap(u / 2, u);
        u /= 2;
    }
}
void down(int u)
{
    int l = u; // l为记录编号
    if (u * 2 <= sizeh && h[u * 2] < h[l])
        l = u * 2; // 与左儿子比较
    if (u * 2 + 1 <= sizeh && h[u * 2 + 1] < h[l])
        l = u * 2; // 与右儿子比较
    if (u != l)    // 发生交换
    {
        heap_swap(u, l); // 交换元素
        down(l);         // l已经变为儿子，继续向下交换
    }
}
int main()
{
    int n, m = 0; // m表示第几个插入的数
    scanf("%d", &n);
    while (n--)
    {
        char op[10];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            sizeh++;                     // 空间++（二叉树中的序号）
            m++;                        // 插入数++（第m个插入的数）
            ph[m] = sizeh, hp[sizeh] = m; // 设置两个指针

            h[sizeh] = x; // 插入模板操作
            up(sizeh);
        }
        else if (!strcmp(op, "PM")) // 获取根节点最小元素输出
            printf("%d\n", h[1]);
        else if (!strcmp(op, "DM")) // 删除最小元素
        {
            heap_swap(1, sizeh);
            sizeh--;
            down(1);
        }
        else if (!strcmp(op, "D")) // 删除第k个插入的数
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, sizeh);
            sizeh--;
            down(k), up(k);
        }
        else  //修改第k个插入的数
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}